package SecondWeek;

public class Sunday {
    // 371、两整数之和
    public int getSum(int a, int b) {
        while (b != 0) {
            int x = a ^ b;
            int carray = (a & b) << 1; // 进位
            a = x;
            b = carray;
        }
        return a;
    }

    // 268、丢失的数字
    public int missingNumber(int[] nums) {
        //位运算
        int ret = 0;
        for (int x : nums) {
            ret ^= x;
        }
        for (int i = 0; i <= nums.length; i++) {
            ret ^= i;
        }
        return ret;
    }

    // 面试题01.01.判定字符是否唯一
    public boolean isUnique(String astr) {
        // 这个字符串里一共只能出现26位的先写字母，如果全出现并且长度超过26了，就说明出现重复的了，就不用判断了直接返回
        // 这个就是 鸽巢原理的优化
        int len = astr.length();
        if (len > 26) {
            return false;
        }

        // 使用 位图 代替 哈希表，0为不存在1为存在
        int bitMap = 0;
        for (int i = 0;i < len;i++) {
            int x = astr.charAt(i) - 'a';
            if ((bitMap & (1 << x)) != 0) {
                return false;
            }else {
                bitMap |= (1 << x);
            }
        }
        return true;
    }

    // 260、只出现一次的数字III
    public int[] singleNumber(int[] nums) {
        // 先对其所有元素进行 异或 操作得到sum
        int sum = 0;
        for (int num : nums) {
            sum ^= num;
        }

        // 因为存在两个不同的值，所以sum不会为0，对于这个sum是两个不同的值进行的 异或
        // 那么这个值的最右面出现的1，就是两个不同的值出现的差异，为0或为1，这样根据这个位置的0或1进行区分
        // 把所有的数据分成两份，一份的那个位置为0，另一份为1，这样就可以区分了
        // sum & (-sum)会把最右面的1取出来
        int k = (sum == Integer.MIN_VALUE ? sum : sum & (-sum));
        int[] ret = new int[2];
        for (int num : nums) {
            if ((num & k) != 0) {
                ret[0] ^= num;
            }else {
                ret[1] ^= num;
            }
        }
        return ret;
    }

    // 461、汉明距离
    public int hammingDistance(int x, int y) {
        int n = x ^ y;
        int ret = 0;
        while (n != 0) {
            n &= (n - 1);
            ret++;
        }
        return ret;
    }

    // 338、比特位计数
    public int[] countBits(int n) {
        // 这个同样是去除最右面的1，之后进行计数
        int[] ret = new int[n + 1];

        for (int i = 0;i <= n;i++) {
            int count = 0;
            int binary = i;
            while (binary != 0) {
                binary &= (binary - 1);
                count++;
            }
            ret[i] = count;
        }
        return ret;
    }

    // 191、位1的个数
    public int hammingWeight(int n) {
        // 根据输入的数，每次去掉二进制的最右面的一个数字
        // n: 1011
        //n & (n - 1) -> 1011 & (1011 - 0001) = 1010，这个数字再赋给n，进行循环处理直至n为0
        int ret = 0;
        while (n != 0) {
            n &= (n - 1);
            ret++;
        }
        return ret;
    }
}
